import javax.print.DocFlavor;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: mac
 * Date: 2022-09-29
 * Time: 17:59
 */
class TreeNode{
    int val;
    TreeNode left;
    TreeNode right;

    public TreeNode(int val) {
        this.val = val;
    }
}
public class Day9 {
    //111.二叉树的最小深度 - 标记
    public int minDepth1(TreeNode root) {
        if (root  == null){
            return 0;
        }
        int leftTree = minDepth1(root.left) + 1;
        int rightTree = minDepth1(root.right) + 1;

        if (leftTree == 1){
            return rightTree;
        }else if (rightTree == 1){
            return leftTree;
        }else{
            return Math.min(leftTree, rightTree);
        }
    }
    public int minDepth(TreeNode root) {
        int cnt = 0;
        if (root == null) return cnt;

        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);

        while (!queue.isEmpty()){
            int size = queue.size();
            cnt++;
            while (size > 0){
                TreeNode cur = queue.poll();
                if (cur.left == null && cur.right == null){
                    return cnt;
                }
                if (cur.left != null) {
                    queue.offer(cur.left);
                }
                if (cur.right != null){
                    queue.offer(cur.right);
                }
                size--;
            }
        }
        return cnt;
    }

    //112.路径总和
    public boolean hasPathSum(TreeNode root, int targetSum) {
        if (root == null){
            return false;
        }
        if (root.left == null && root.right == null){
            return targetSum - root.val == 0;
        }
        return hasPathSum(root.left, targetSum - root.val) || hasPathSum(root.right, targetSum - root.val);
    }

    //257.二叉树的所有路径 - 标记
    public void getList(TreeNode root, StringBuilder sb, List<String> ret){
        if (root == null){
            return;
        }
        sb.append(root.val);
        if (root.left == null && root.right == null){
            ret.add(sb.toString());
        }else{
            sb.append("->");
            getList(root.left, new StringBuilder(sb), ret);
            getList(root.right,new StringBuilder(sb), ret);
        }
    }
    public List<String> binaryTreePaths(TreeNode root) {
        List<String> list = new ArrayList<>();
        if (root == null){
            return list;
        }
        StringBuilder sb = new StringBuilder();
        getList(root,sb, list);
        return list;
    }

    //404.左叶子之和 - 标记
    public int sumOfLeftLeaves(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int ret = 0;
        if (root.left != null && root.left.left == null && root.left.right == null){
            ret += root.left.val;
        }
        return sumOfLeftLeaves(root.left) + sumOfLeftLeaves(root.right) + ret;
    }

    //501.二叉搜索树中的众数 - 标记
    int preVal = 0, curTimes = 0, maxTimes = 0;
    ArrayList<Integer> ret = new ArrayList<>();
    public int[] findMode(TreeNode root) {
        getMode(root);
        int size = ret.size();
        int[] cnt = new int[size];
        for (int i = 0; i < size; i++) {
            cnt[i] = ret.get(i);
        }
        return cnt;
    }
    public void getMode(TreeNode root) {
        if (root != null){
            getMode(root.left);

            if (root.val == preVal){
                curTimes++;
            }else{
                preVal = root.val;
                curTimes = 1;
            }

            if (curTimes == maxTimes){
                ret.add(root.val);
            }else if (curTimes > maxTimes){
                ret.clear();
                ret.add(root.val);
                maxTimes = curTimes;
            }
            getMode(root.right);
        }
    }

    //530.二叉搜索树的最小绝对差
    int min = 10000;
    public TreeNode preNode = null;
    ArrayList<Integer> list = new ArrayList<>();
    public int getMinimumDifference(TreeNode root) {
        getMin(root);
        return min;
    }
    public void getMin(TreeNode root){
        if (root == null){
            return;
        }
        getMin(root.left);
        if (preNode != null){
            min = Math.min(Math.abs(root.val - preNode.val),min);
        }
        preNode = root;
        getMin(root.right);
    }
}
